/**
 * @author ChaP
 * @date 2019/04/18
 * @describe:
 */
package CodingTest.AC20190418;

/**
 * leetcode - 377
 * 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

 示例:

 nums = [1, 2, 3]
 target = 4

 所有可能的组合为：
 (1, 1, 1, 1)
 (1, 1, 2)
 (1, 2, 1)
 (1, 3)
 (2, 1, 1)
 (2, 2)
 (3, 1)

 请注意，顺序不同的序列被视作不同的组合。

 因此输出为 7。
 */
public class combinationSum4 {
    //递归 超出规定时间
    public int combinationSum4(int[] nums, int target) {
        if (target == 0) {
            return 1;
        }
        int res = 0;
        for(int num:nums){
            if(target>= num){
                res+=combinationSum4(nums,target-num);
            }
        }
        return res;
    }
    //动态规划
    public int combinationSum4_1(int[] nums, int target) {
       int[] dp = new int[target+1];
       for(int i =0;i<=target;i++){
           for(int num:nums){
               if(i>num){
                   dp[i]+=dp[i-num];
               }
           }
       }
       return target;
    }



    public static void main(String[] args) {
        combinationSum4 cb = new combinationSum4();
        int[] nums = {1,2,3};
        System.out.println(cb.combinationSum4_1(nums,7));
    }
}
